#ifndef _PRIORITY_QUEUE_H
#define _PRIORITY_QUEUE_H

#include <iostream>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>

using std::vector;
using std::map;
using std::string;
using std::cout;
using std::endl;
using std::ostream;

template <typename T>
class PriorityQueue {
	vector<T> heap;
	map<T, int> index;
	int n;

	int parent(int i) const {
		return i/2;
	}

	int left(int i) const {
		return 2*i;
	}

	int right(int i) const {
		return 2*i+1;
	}

	void swap(int i, int j) {
		T tmp = heap[i];
		heap[i] = heap[j];
		heap[j] = tmp;
		index[heap[i]] = i;
		index[heap[j]] = j;
	}

	void heapify(int i) {
		int l = left(i);
		int r = right(i);
		int m = l <= n && heap[l] < heap[i] ? l : i;
		if (r <= n && heap[r] < heap[m])
			m = r;
		if (m != i) {
			swap(i, m);
			heapify(m);
		}
	}

	void heapify_up(int i) {
		while (i > 1 && heap[i] < heap[parent(i)]) {
			swap(i, parent(i));
			i = parent(i);
		}
	}

	void print() {
		for (int i = 1; i <= n; ++i)
			cout << heap[i] << ", ";
		cout << endl;
	}
	
	public:

	PriorityQueue() : n(0) {
		heap.push_back(T());
	}

	PriorityQueue(const vector<T>& elements) : n(elements.size()) {
		heap.push_back(T());
		heap.insert(heap.end(), elements.begin(), elements.end());

		for (int i = 1; i <= n; ++i)
			index[heap[i]] = i;
		for (int i = n/2; i >= 1; --i)
			heapify(i);
	}

	bool empty() const {
		return n == 0;
	}

	void push(const T& e) {
		heap.push_back(e);
		index[e] = ++n;
		heapify_up(n);
		print();
	}

	bool pop(T& e) {
		if (!n)
			return false;
		e = heap[1];
		swap(1, n);
		heap.pop_back();
		index.erase(e);
		--n;
		heapify(1);
		return true;
		
	}

	int size() const {
		return n;
	}

	void key_changed(const T& e) {
		int i = index[e];
		heapify_up(i);
		heapify(i);
	}
};

#endif

